package dp.打家劫舍;

public class leetcode740删除并获得点数 {
    // 打架劫舍问题变形，打家劫舍问题核心思想，数组元素无法选相邻，求最大
    public int deleteAndEarn(int[] nums) {
        if (nums == null ||nums.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            max = Integer.max(max, nums[i]);
        }
        int[] sum = new int[max + 1];
        for (int i = 0; i < length; i++) {
            sum[nums[i]] += nums[i];
        }
        return rob(sum);
    }

    private int rob(int[] sum) {
        int length = sum.length;
        if (length == 1) {
            return sum[0];
        }
        int pre = sum[0];
        int cur = Integer.max(sum[0], sum[1]);
        for (int i = 2; i < length; i++) {
            int temp = cur;
            cur = Integer.max(cur, pre + sum[i]);
            pre = temp;
        }
        return cur;
    }
}
